{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PlhRSC3iWzA1"
      },
      "source": [
        "```\n",
        "- Copyright 2023 DeepMind Technologies Limited\n",
        "- All software is licensed under the Apache License, Version 2.0 (Apache 2.0); you may not use this file except in compliance with the Apache 2.0 license. You may obtain a copy of the Apache 2.0 license at: https://www.apache.org/licenses/LICENSE-2.0\n",
        "- All other materials are licensed under the Creative Commons Attribution 4.0 International License (CC-BY).  You may obtain a copy of the CC-BY license at: https://creativecommons.org/licenses/by/4.0/legalcode\n",
        "- Unless required by applicable law or agreed to in writing, all software and materials distributed here under the Apache 2.0 or CC-BY licenses are distributed on an \\\"AS IS\\\" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the licenses for the specific language governing permissions and limitations under those licenses.\n",
        "- This is not an official Google product\n",
        "```"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3LCquqjVWy0e"
      },
      "source": [
        "# Cyclic graphs\n",
        "\n",
        "This notebook contains:\n",
        "1. the *skeleton* we used for FunSearch to discover large independent sets in the $n$-th strong product of cyclic graphs,\n",
        "2. the *functions* discovered by FunSearch that construct those independent sets.\n",
        "\n",
        "## Skeleton\n",
        "\n",
        "The commented-out decorators are just a way to indicate the main entry point of the program (`@funsearch.run`) and the function that *FunSearch* should evolve (`@funsearch.evolve`)."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "aIkfPyeLXB4n"
      },
      "outputs": [],
      "source": [
        "\"\"\"Obtains maximal independent sets.\"\"\"\n",
        "import itertools\n",
        "import numpy as np\n",
        "\n",
        "\n",
        "# @funsearch.run\n",
        "def evaluate(num_nodes: int, n: int) -\u003e int:\n",
        "  \"\"\"Returns the size of an independent set.\"\"\"\n",
        "  independent_set = solve(num_nodes, n)\n",
        "  return len(independent_set)\n",
        "\n",
        "\n",
        "def solve(num_nodes: int, n: int) -\u003e list[tuple[int, ...]]:\n",
        "  \"\"\"Gets independent set with maximal size.\n",
        "\n",
        "  Args:\n",
        "    num_nodes: The number of nodes of the base cyclic graph.\n",
        "    n: The power we raise the graph to.\n",
        "\n",
        "  Returns:\n",
        "    A list of `n`-tuples in `{0, 1, 2, ..., num_nodes - 1}`.\n",
        "  \"\"\"\n",
        "  to_block = np.array(list(itertools.product([-1, 0, 1], repeat=n)))\n",
        "\n",
        "  # Powers in decreasing order for compatibility with `itertools.product`, so\n",
        "  # that the relationship `i = children[i] @ powers` holds for all `i`.\n",
        "  powers = num_nodes ** np.arange(n - 1, -1, -1)\n",
        "\n",
        "  # Precompute the priority scores.\n",
        "  children = np.array(\n",
        "      list(itertools.product(range(num_nodes), repeat=n)), dtype=np.int32)\n",
        "  scores = np.array([priority(tuple(child), num_nodes, n)\n",
        "                     for child in children])\n",
        "\n",
        "  # Build `max_set` greedily, using scores for prioritization.\n",
        "  max_set = np.empty(shape=(0, n), dtype=np.int32)\n",
        "  while np.any(scores != -np.inf):\n",
        "    # Add a child with a maximum score to `max_set`, and set scores of\n",
        "    # invalidated children to -inf, so that they never get selected.\n",
        "    max_index = np.argmax(scores)\n",
        "    child = children[None, max_index]  # [1, n]\n",
        "\n",
        "    blocking = np.einsum(\n",
        "        'cn,n-\u003ec', (to_block + child) % num_nodes, powers)  # [C]\n",
        "    scores[blocking] = -np.inf\n",
        "    max_set = np.concatenate([max_set, child], axis=0)\n",
        "\n",
        "  return [tuple(map(int, el)) for el in max_set]\n",
        "\n",
        "\n",
        "# @funsearch.evolve\n",
        "def priority(el: tuple[int, ...], num_nodes: int, n: int) -\u003e float:\n",
        "  \"\"\"Returns the priority with which we want to add `el` to the set.\n",
        "\n",
        "  Args:\n",
        "    el: an n-tuple representing the element to consider whether to add.\n",
        "    num_nodes: the number of nodes of the base graph.\n",
        "    n: an integer, power of the graph.\n",
        "\n",
        "  Returns:\n",
        "    A number reflecting the priority with which we want to add `el` to the\n",
        "    independent set.\n",
        "  \"\"\"\n",
        "  return 0."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aLkn0zVUYSbk"
      },
      "source": [
        "By executing the skeleton with the trivial `priority` function in place we can check that the resulting independent sets are far from optimal (e.g., the best known construction for the 5th strong product of the 7-node graph has size 367):\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "executionInfo": {
          "elapsed": 75,
          "status": "ok",
          "timestamp": 1697104375004,
          "user": {
            "displayName": "",
            "userId": ""
          },
          "user_tz": -60
        },
        "id": "9t9out8lYBSr",
        "outputId": "5ac9c2b2-e066-44af-947e-c94b4b826421"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "1 3\n",
            "2 9\n",
            "3 27\n",
            "4 81\n",
            "5 243\n"
          ]
        }
      ],
      "source": [
        "for n in range(1, 6):\n",
        "  print(n, evaluate(num_nodes=7, n=n))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "FBbvHTaQY3X8"
      },
      "source": [
        "## Discovered function that builds an independent set of size $367$ in $C_7^5$\n",
        "\n",
        "This matches the size of the best known construction by [Polak \u0026 Schrijver (2019)](https://ir.cwi.nl/pub/30364/30364.pdf)."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "w4yMoDAoYjYq"
      },
      "outputs": [],
      "source": [
        "def priority(el: tuple[int, ...], num_nodes: int, n: int) -\u003e float:\n",
        "  \"\"\"Returns the priority with which we want to add `el` to the set.\"\"\"\n",
        "  score = 0.\n",
        "  for i in range(n):\n",
        "    if el[i] == el[(i + 2) % n]:\n",
        "      score += 1\n",
        "    else:\n",
        "      score -= 1\n",
        "    x = ((n - 2) * el[i] - el[(i + 1) % n]\n",
        "         - el[(i + 2) % n] - (n + 1) * el[(i + 3) % n]) % num_nodes\n",
        "    score -= 0.5 * (x - el[(i + 1) % n]) ** 2\n",
        "    score += 0.1 * (num_nodes - 1 - (x - 1) % num_nodes) ** 2\n",
        "    score += 0.2 * (num_nodes - 1 - (x - 2) % num_nodes) ** 2\n",
        "  return score"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "A_eiYDIsZLYi"
      },
      "outputs": [],
      "source": [
        "assert evaluate(num_nodes=7, n=5) == 367"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "zfY5hIZnZYQg"
      },
      "source": [
        "## Discovered function that builds the best known independent sets in $C_9^n$ for $n=3,...,7$\n",
        "\n",
        "These independent sets match the best known construction reported by [Matthew \u0026 Östergård (2016)](https://link.springer.com/article/10.1007/s10623-016-0194-7)."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "al23ssPbZUpk"
      },
      "outputs": [],
      "source": [
        "def priority(el: tuple[int, ...], num_nodes: int, n: int) -\u003e float:\n",
        "  \"\"\"Returns the priority with which we want to add `el` to the set.\"\"\"\n",
        "  s = 0.\n",
        "  for i in range(n):\n",
        "    s += el[i] \u003c\u003c i\n",
        "    s %= num_nodes\n",
        "  return (2 * el[2] - 4 * el[0] + el[1]) % num_nodes + s"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0li-u2bKzcqs"
      },
      "source": [
        "Below, we only run the code up until $n=5$. Uncomment the line below to run also the code with $n=6$ and $n=7$, which would take about 10 minutes to execute."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "4tiBK2mzadTA"
      },
      "outputs": [],
      "source": [
        "expected_sizes = {\n",
        "    3: 81,\n",
        "    4: 324,\n",
        "    5: 1458,\n",
        "    6: 6561,\n",
        "    7: 26244\n",
        "}\n",
        "range_n = range(3, 6)\n",
        "# range_n = range(3, 8)  # Uncomment to run up until n=7.\n",
        "for n in range_n:\n",
        "  assert evaluate(num_nodes=9, n=n) == expected_sizes[n]"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "m1pW8OYnarxM"
      },
      "source": [
        "## Discovered function that finds an independent set of size 754 in $C_{11}^4$\n",
        "\n",
        "This is larger than the best known independent set reported by [Matthew \u0026 Östergård (2016)](https://link.springer.com/article/10.1007/s10623-016-0194-7), which has size $748$."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "mDrmnumFah_t"
      },
      "outputs": [],
      "source": [
        "def priority(el: tuple[int, ...], num_nodes: int, n: int) -\u003e float:\n",
        "  \"\"\"Returns the priority with which we want to add `el` to the set.\"\"\"\n",
        "  el_clipped = np.clip(el, a_min=None, a_max=num_nodes - 3)\n",
        "  values = 2 * np.array(list(itertools.product(range(1, n), repeat=n)))\n",
        "  multipliers = np.array(\n",
        "      [num_nodes ** i for i in range(n - 1, -1, -1)], dtype=np.int32)\n",
        "  x = np.sum((1 + values + el_clipped) * multipliers, axis=-1)\n",
        "  return np.sum(x % (num_nodes - 2), dtype=float)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "dvRR69L-bD95"
      },
      "outputs": [],
      "source": [
        "assert evaluate(num_nodes=11, n=4) == 754"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}
